#include <stdio.h>

//二分查找 binary search  /half search
/*
 * 对于一个有序数列而言，我们可以采用二分查找。
 * 思想：我们将搜索范围的中间值作为参考值，与待查找的值进行对比。
 * 根据对比结果，我们可以至少缩小一半的查找范围。
 *
 * 假设数组为升序或者非降序数组
 * 设置两个指针（两个指向下标值的变量）L和H，分为指向搜索范围的最低位下标值和最高位下标值
 * 中间位置的指针（中间位置的下标值）mid =(L+H)/2;
 * while(L<=H)//L<=H 意味着搜索范围还存在，在没有找到的情况下可以继续进行查找
 * {
 * 然后和传入的值value进行比较：
 *    如果 value >arr[mid],证明搜索范围向右，则移动最低位的指针到中间值的后一位即L=mid+1;
 *    如果 value < arr[mid],证明搜索范围向左，则移动最高位的指针到中间值的前一位即H= mid-1;
 *    如果 value == arr[mid] 证明找到，return 1或者mid
 *    }
 * */
/*
 * 函数名：binarySearch
 * 输入：升序/非降序的数组arr,待查找的值
 * 输出：找到 返回下标值  没找到 -1
 *
 * arr[]:数组
 * value:待查找值
 * low:搜索范围的最低位下标
 * high:搜索范围的最高位下标
 * */

int binarySearch(int arr[],int value,int low ,int high){
    int mid;
    while(low<=high){
        mid = (low+high)/2;
        if(value>arr[mid]){
            low = mid+1;
        } else if(value <arr[mid]){
            high = mid -1;
        } else
            return mid;
    }
    return -1;
}


int main() {
    int arr[] ={1,2,3,4,5,6,7,8,9};
    int value =23;
    int tmp = binarySearch(arr,value,0,8);
    if(tmp!=-1)
        printf("值%d的下标值位%d\n",value,tmp);
    else
        printf("值没找到");
    //printf("Hello, World!\n");
    return 0;
}
